Información del Plan Docente

1. Información Básica

1.1. Objetivos de la asignatura

La asignatura y sus resultados previstos responden a los siguientes planteamientos y objetivos:

Se trata de una asignatura de formación básica dentro del Grado de Matemáticas, y uno de los principales objetivos es que los conocimientos teóricos y las técnicas adquiridas sirvan como base para asignaturas de cursos posteriores.

Por otra parte, en la modelización, formulación, análisis y resolución de muchos problemas científicos, se requiere conocer los métodos de Teoría de Grafos y se necesitan las herramientas de análisis combinatorio. Por ello, otro de los objetivos de la asignatura es saber reconocer este tipo de problemas y saber aplicar las técnicas adecuadas para su resolución.

Finalmente, la asignatura tiene un gran valor formativo, ya que sirve para desarrollar la capacidad analítica, la capacidad de abstracción y el pensamiento lógico

1.2. Contexto y sentido de la asignatura en la titulación

Se trata de una asignatura del módulo Matemática Discreta y Optimización dedicada esencialmente al estudio de estructuras discretas y a problemas de enumeración. Para su correcto desarrollo se requieren conocimientos básicos de álgebra lineal y análisis matemático.

En muchas materias del ámbito de las matemáticas los problemas subyacentes son de tipo combinatorio, por ello una base sólida en combinatoria es esencial en casi todas las ramas clásicas de las matemáticas, como probabilidad, geometría, álgebra,…

Por otra parte, las estructuras discretas de grafos y árboles aparecen de forma natural en las materias de Informática. Señalar por último, que también dentro del campo de la Informática, para el análisis de la complejidad computacional de algoritmos se necesita conocer y manejar los métodos de enumeración.

1.3. Recomendaciones para cursar la asignatura

El estudio y trabajo continuado son esenciales para superar la asignatura. Se recomienda en particular la realización de los ejercicios propuestos. Una de las dificultades de la asignatura, sobre todo en los temas de combinatoria, radica en la dificultad de distinguir los conjuntos sobre los que se trabaja, de precisar que elementos los forman. La consulta de dudas al profesor y la clarificación de conceptos son fundamentales para progresar en la materia.

2. Competencias y resultados de aprendizaje

2.1. Competencias

Al superar la asignatura, el estudiante será más competente para:

• Desenvolverse en el manejo de los objetivos descritos (Ver apartado Resultados de aprendizaje).
• Resolver problemas matemáticos mediante habilidades de cálculo combinatorio y técnicas de teoría de grafos.
• Proponer, analizar, validar e interpretar modelos de situaciones reales sencillas, utilizando las herramientas matemáticas adecuadas a los fines que se persigan.
• Comprender y utilizar el lenguaje y método matemáticos.
• Conocer demostraciones rigurosas de los teoremas básicos de combinatoria y teoría de grafos.
• Aprender nuevos conocimientos y técnicas matemáticas de forma autónoma.
• Haber desarrollado habilidades de aprendizaje necesarias para emprender estudios posteriores en matemáticas con un alto grado de autonomía.

2.2. Resultados de aprendizaje

El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados:

• Es capaz de resolver problemas elementales de ordenación y enumeración.
• Conoce y maneja el concepto de función generatriz y el de fórmula de recurrencia.
• Es capaz de utilizar las funciones generatrices para obtener fórmulas para problemas de enumeración.
• Conoce el lenguaje y las aplicaciones más elementales de la teoría de grafos.
• Es capaz de aplicar los algoritmos básicos de teoría de grafos para resolver problemas.

2.3. Importancia de los resultados de aprendizaje

Proporcionan una formación de carácter básico dentro del grado (ver Contexto y sentido de la asignatura en la titulación).

Además, los problemas de tipo combinatorio, son probablemente los problemas matemáticos más frecuentes en situaciones cotidianas, como organización de turnos y horarios, distribuciones de personas en grupos, realización de sorteos, muestreo, etc. Ser capaz de resolver esos problemas básicos de combinatoria de forma clara y precisa es uno de los resultados del aprendizaje.

De la misma forma, los grafos o redes, son una de las estructuras matemáticas más frecuentes en situaciones reales, y conocer sus propiedades y los algoritmos básicos para resolución de problemas sobre ellos, es fundamental para la formación de un matemático.

3. Evaluación

3.1. Tipo de pruebas y su valor sobre la nota final y criterios de evaluación para cada prueba

El estudiante deberá demostrar que ha alcanzado los resultados de aprendizaje previstos mediante las siguientes actividades de evaluación:

Para superar esta asignatura hay que obtener al menos 50 puntos. Hay dos opciones:

• Solo examen final (100 puntos).
• Puntos de clase (20 puntos) + Examen final (80 puntos, distinto del anterior, mínimo 32 puntos).

Los puntos de clase se obtienen por realización de los ejercicios propuestos a cada estudiante (4 series de problemas).

4. Metodología, actividades de aprendizaje, programa y recursos

4.1. Presentación metodológica general

El proceso de aprendizaje que se ha diseñado para esta asignatura se basa en lo siguiente:

Clases de teoría. Consisten en lecciones impartidas por el profesor siguiendo principalmente el modelo de lección magistral, utilizando el apoyo de medios audiovisuales y recursos informáticos cuando sea conveniente, y procurando también cierta interacción con los estudiantes. Como máximo supondrán el 50% de las clases.

Técnicas y herramientas para la resolución de problemas. Se enseñarán técnicas de resolución de ejercicios y problemas en clase. Se propondrán también problemas y ejercicios, personales o en grupos reducidos. Estas actividades implican que los estudiantes tendrán que realizar por su parte un trabajo personal para la resolución de los problemas propuestos y la redacción de soluciones. Supondrán al menos el 40% de las clases.

Seminarios tutelados de teoría/problemas. En estos seminarios los estudiantes plantearán las dudas y dificultades con las que se han encontrado, de manera que el papel del profesor consistirá en dar indicaciones específicas que desbloqueen la situación.

Tutorías. Además de los horarios de tutorías personales establecidos por el profesor, los estudiantes dispondrán también de una dirección de correo electrónico para hacer consultas.

Trabajo personal. El estudio individual le permitirá asentar los conceptos explicados en las clases, así como aprender y aplicar adecuadamente las técnicas explicadas. También dedicará una parte importante de su tiempo a la resolución de los ejercicios propuestos.

La asignatura aparece en el Anillo Digital Docente (ADD) de la Universidad de Zaragoza. Así, el alumno puede obtener información sobre la asignatura, apuntes, material complementario, hojas de problemas, etc.

4.2. Actividades de aprendizaje

• Clases de teoría y problemas, realización de ejercicios, tutorías y seminarios sobre los siguientes tópicos: Combinatoria elemental, Funciones generatrices, Grafos, Camino óptimo y Problemas de flujo.
• Apoyo a la formación mediante documentos y enlaces  en la página de la asignatura en el ADD de la universidad, moodle.unizar.es (acceso restringido  a los alumnos matriculados).

Las actividades docentes y de evaluación se llevarán a cabo de modo presencial salvo que, debido a la situación sanitaria, las disposiciones emitidas por las autoridades competentes y por la Universidad de Zaragoza dispongan realizarlas de forma telemática o semitelemática con aforos reducidos rotatorios.

4.3. Programa

TEMA I

1. Combinatoria elemental: Permutaciones y combinaciones.
2. Coeficientes binomiales.
3. Recurrencias. Aplicaciones.
4. El principio de inclusión-exclusión. Aplicaciones.

TEMA II

5. Funciones generatrices.
6. Funciones generatrices racionales.

TEMA III

7. Definición y notaciones para grafos.
8. Problema de recorrido de un grafo. Algoritmos  BFS y DFS.
9. Aplicaciones. Cálculo de componentes y bases.
10. Número de árboles y caminos de un grafo.

TEMA IV

11. Grafos con costos. Algoritmos para calcular el árbol mínimo.
12. Caminos más cortos: Algoritmo de Dijkstra.
13. Técnicas PERT-CPM de planificación de proyectos.

TEMA V

14. Flujo en redes. Conceptos básicos.
15. Algoritmo de Ford- Fulkerson para cálculo de máximo flujo.
16. Teoremas de conectividad de Menger.
17. Matching en grafos bipartitos.
18. Algunos problemas NP-duros sobre grafos. 

4.4. Planificación de las actividades de aprendizaje y calendario de fechas clave

Calendario de sesiones presenciales y presentación de trabajos:

• Las clases magistrales y de problemas (hasta 4 horas a la semana) se imparten según horario establecido por el centro, publicado con anterioridad a la fecha de comienzo del curso.
• En principio habrá cuatro series de ejercicios para realizar de forma individual. Se realizarán sesiones de seminario donde cada grupo de alumnos recibirá orientación especializada para la resolución de dudas, clarificación de enunciados y realización de esos ejercicios propuestos. Los horarios de estas sesiones y las fechas límite de entrega de cada serie de ejercicios se publicarán con suficiente antelación.
• Realización de un examen escrito a final de cuatrimestre, en fecha determinada por el centro.
• Realización, de forma individual, de ejercicios correspondientes a las distintas partes de la asignatura.
• Desde el primer día de clase los alumnos dispondrán de un calendario detallado de fechas de exámenes y fechas de entrega de los ejercicios propuestos.

4.5. Bibliografía y recursos recomendados

La bibliografía recomendada es la siguiente:

Básica: Apuntes de la asignatura. Disponibles online en la página de la asignatura en el ADD.

Complementaria:

• Bóna, Miklós. A walk through combinatorics : an introduction to enumeration and graph theory / Miklos Bona . - 2nd ed.. Hackensack: World Scientific, 2008.
• Brualdi, Richard A. : Introductory combinatorics / Richard A. Brualdi . - 5th ed. Upper Saddle River, New Jersey : Pearson Prentice Hall, cop. 2010.
• Gross, Jonathan L.. Graph theory and its applications / Jonathan Gross, Jay Yellen . - 2nd ed. Boca Raton : Chapman & Hall/CRC, 2006.
• Lint, Jacobus Hendricus Van. A course in combinatorics / J. H. van Lint and R. M. Wilson . - [1st Ed., 2nd. repr.] Cambridge : Cambridge University Press, 1996.
• Pemmaraju, Sriram. Computational discrete mathematics : combinatorics and graph theory with mathematica / Sriram Pemmaraju, Steven Skiena . 1st publ., repr. Cambridge : Cambridge University Press, 2009.
• Stanley, Richard P.. Enumerative combinatorics / Richard P. Stanley . Cambridge ; New York : Cambridge University Press, cop. 1997-1999.

Información sobre la asignatura, con programa detallado, calendario, apuntes de la asignatura, hojas de problemas, etc., puede hallarse en la página de la asignatura en el ADD.

Otros enlaces con material y recursos interesantes sobre combinatoria y teoría de grafos son:

• http://dimacs.rutgers.edu/%7Ehochberg/undopen/
• http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html
• Discrete Mathematics Web Site!
• http://www.research.att.com/~njas/sequences/
• http://www.math.fau.edu/locke/graphthe.html
• http://diestel-graph-theory.com/index.html
• http://www.math.upenn.edu/~wilf/DownldGF.html

http://psfunizar10.unizar.es/br13/egAsignaturas.php?codigo=27005